package test.n00000;


public class Problem00041 {
    public static void main(String[] args) {
        println(new int[]{}, new int[]{1});
        println(new int[]{1, 3}, new int[]{2});
        println(new int[]{1, 2}, new int[]{3, 4});
    }


    public static void println(int[] nums1, int[] nums2) {
        Solution s = new Solution();
        System.out.println(s.findMedianSortedArrays(nums1, nums2));
    }

    public static class Solution {
        /**
         * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
         * <p>
         * 算法的时间复杂度应该为 O(log (m+n)) 。
         * <p>
         * 来源：力扣（LeetCode）
         * 链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
         * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
         * <p>
         * 解题思路:
         * 二分查找法
         * 用两个指针，找到两个数据中对应的中位数
         */
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int sumLen = nums1.length + nums2.length;

            if (sumLen % 2 == 0) {
                return (middleElement(nums1, nums2, sumLen / 2 - 1) + middleElement(nums1, nums2, sumLen / 2)) / 2.0;
            } else {
                return middleElement(nums1, nums2, sumLen / 2);

            }
        }

        public int middleElement(int[] nums1, int[] nums2, int position) {
            int r = 0;
            int p1 = 0, p2 = 0;

            while (position-- >= 0) {

                if (p1 < nums1.length && p2 < nums2.length && nums1[p1] < nums2[p2]) {
                    r = nums1[p1];
                    p1++;
                    continue;
                }

                if (p1 < nums1.length && p2 < nums2.length && nums1[p1] > nums2[p2]) {
                    r = nums2[p2];
                    p2++;
                    continue;
                }

                if (p1 < nums1.length) {
                    r = nums1[p1];
                    p1++;
                    continue;
                }

                if (p2 < nums2.length) {
                    r = nums2[p2];
                    p2++;
                    continue;
                }
            }
            return r;
        }
    }
}
